//迷宫找出口
https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/

class Solution {
public:
    using PII = pair<int, int>;
    int _x[4] = {0, 0, 1, -1};
    int _y[4] = {1, -1, 0, 0};
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) 
    {
        int n = maze.size();
        int m = maze[0].size();
        int ret = 0;
        queue<PII> q;
        vector<vector<bool>> check(n,vector<bool>(m));
        q.push(make_pair(entrance[0],entrance[1]));
        check[entrance[0]][entrance[1]] = true;

        while(!q.empty())
        {
            ret++;
            int size = q.size();
            while(size--)
            {
                PII top = q.front();
                q.pop();
                for(int i = 0; i < 4; i++)
                {
                    int xpos = top.first + _x[i];
                    int ypos = top.second + _y[i];                  
                    if(xpos >= 0 && xpos < n && ypos >= 0 && ypos < m 
                    && maze[xpos][ypos] == '.' && check[xpos][ypos] == false)
                    {
                        cout << xpos << " " << ypos << endl;
                        if(xpos == 0 || xpos == n - 1 || ypos == 0 || ypos == m - 1) return ret;
                        check[xpos][ypos] = true;
                        q.push(make_pair(xpos,ypos));
                    }
                }
            }
        }
        return -1;
    }
};
};